๋ฌธ์
๐ Logic
private void bfs(int x, int y) {}
private int find(int n) {}
private void merge(int n1, int n2) {}
-
BFS๋ฅผ ์ํํด์ ์งํ๋ณ๋ก ๋ฒํธ๋ฅผ ๋งค๊ธด๋ค.
- ์ํํ๋ฉด์, ๋์ด ์ฐจ๊ฐ ํฐ ์งํ์ ์ฐ์ ์์ ํ์ ๋ฃ์ด์ค๋ค.
- ์ดํ, ๋์ด์ฐจ๋ฅผ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌ๋ ์ฐ์ ์์ ํ์ ์๋ ์ง์ญ์ ํฉ์ณ์ฃผ๋ฉด์ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํด MST๋ฅผ ๊ตฌํ๋ฉด์ ์ฌ๋ค๋ฆฌ์ ์ดํฉ์ ๊ตฌํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
class Square implements Comparable<Square> {
int from;
int to;
int diffDist;
public Square(int from, int to, int diffDist) {
this.from = from;
this.to = to;
this.diffDist = diffDist;
}
@Override
public int compareTo(Square s) {
return Integer.compare(this.diffDist, s.diffDist);
}
}
class Solution {
private static int N;
private static int[] parent;
private static Queue<Square> pq = new PriorityQueue<>();
private static int[][] visited;
private static int[][] land;
private static int height;
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private static int areaN;
public int solution(int[][] land, int height) {
this.N = land.length;
this.height = height;
this.land = land;
this.visited = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (visited[i][j] == 0) {
areaN++;
bfs(i, j);
}
this.parent = new int[areaN + 1];
for (int i = 0; i <= areaN; i++) parent[i] = i;
int answer = 0;
while(!pq.isEmpty()) {
Square s = pq.poll();
int f = s.from;
int t = s.to;
int d = s.diffDist;
// ๊ฐ์ ๋ถ๋ชจ, ์ฆ ์ฌ์ดํด์ ํ์ฑํ๊ฑฐ๋, ํน์ ๋ฐฉ๋ฌธํ ์ ์๋ ์งํ์ด๋ผ๋ฉด ํจ์ค
if (find(f) == find(t) || (f == 0 || t == 0)) continue;
else {
// ๋ถ๋ชจ๋ฅผ ๊ฐ๊ฒ, ์ฆ ์ฌ๋ค๋ฆฌ๋ฅผ ๋๊ณ ์ด๋ํ์์ ์๋ฏธ!
merge(f, t);
answer += d;
}
}
return answer;
}
// ์ด๋ ๊ฐ๋ฅํ ์งํ์ ๋ฒํธ ๋งค๊ธฐ๊ธฐ
private void bfs(int x, int y) {
visited[x][y] = areaN;
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(x, y));
while(!queue.isEmpty()) {
Node node = queue.poll();
int tmpX = node.x;
int tmpY = node.y;
for (int[] d : dir) {
int nx = tmpX + d[0];
int ny = tmpY + d[1];
if (!isIn(nx, ny)) continue;
int diff = Math.abs(land[tmpX][tmpY] - land[nx][ny]);
// ์งํ ๊ฐ์ ์ฐจ๊ฐ ๋์ด๋ณด๋ค ํฌ๊ณ , ์ด๋ฏธ ๋ฐฉ๋ฌธํ ์ง์ญ์ด๋ผ๋ฉด ์ฌ๋ค๋ฆฌ๋ฅผ ๋์์ผ ํ ์๋ ์๋ค.
if (diff > height) {
if (visited[nx][ny] != 0)
pq.offer(new Square(visited[tmpX][tmpY], visited[nx][ny], diff));
continue;
}
// ์งํ ๊ฐ์ ์ฐจ๊ฐ ๋์ด๋ณด๋ค ํฌ์ง ์์ ๊ฒฝ์ฐ,
// ๋ฐฉ๋ฌธํ ์งํ์ด๋ผ๋ฉด ํจ์ค
if (visited[nx][ny] != 0) continue;
// ๋ฐฉ๋ฌธํ ์ ์๋ ์งํ์ธ ๊ฒฝ์ฐ ๋ฒํธ ๋งค๊ธฐ๊ธฐ
else {
visited[nx][ny] = areaN;
queue.offer(new Node(nx, ny));
}
}
}
}
private boolean isIn(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N;
}
// ์ฌ๊ท๋ฅผ ์ด์ฉํด ๋ถ๋ชจ ์งํ ๋ฒํธ ์ฐพ๊ธฐ
private int find(int n) {
if (parent[n] == n) return n;
else return parent[n] = find(parent[n]);
}
private void merge(int n1, int n2) {
n1 = find(n1);
n2 = find(n2);
if (n1 == n2) return;
if (n1 > n2) parent[n1] = n2;
else parent[n2] = n1;
}
}
โ๏ธ Review
- ์ง์ญ์ ๋๋๊ณ , ์๋ก ๋ค๋ฅธ ์ง์ญ์ด ๋ง๋ฟ๋ ๊ณณ์ ํ๋ณด๋ก ์ ์ฅํด๋๊ณ ์ด๊ฒ๋ค์ ๊ฐ์ง๊ณ ์ฌ๋ค๋ฆฌ ๋น์ฉ์ ๊ณ์ฐํด๋ด์ผ๊ฒ ๋ค๋ ์๊ฐ์ ํ์ง๋ง ์ด๋ป๊ฒ ํด์ผํ ์ง ๊ฐ์ด ์ ์กํ๋ค.
- ๊ฒ์ํ์ ์ฐธ๊ณ ํ๋ MST๋ฅผ ๊ตฌํ๋ ๊ฒ์ด ๊ด๊ฑด์ธ ๋ฌธ์ ์๊ณ , ์ฐธ๊ณ ๋ฅผ ํตํด ํด๊ฒฐํ ์ ์์๋ค ...